Ensembles récursivement inséparables
En théorie de la calculabilité, deux ensembles disjoints d'entiers naturels sont appelés récursivement inséparables s'ils ne peuvent pas être "séparés" par un ensemble récursif[1],[2],[3].
Définition[modifier | modifier le code]
Les entiers naturels sont l'ensemble . Étant donné deux sous-ensembles disjoints A et B de , un ensemble séparateur C est un sous-ensemble de tel que A ⊆ C et B ∩ C = ∅ (ou de manière équivalente, A ⊆ C et B ⊆ C). Par exemple, A lui-même est un ensemble séparateur pour la paire, tout comme B.
Si une paire d'ensembles disjoints A et B n'a pas d'ensemble séparateur récursif, alors les deux ensembles sont récursivement inséparables.
Exemples[modifier | modifier le code]
Si A est un ensemble non récursif, alors A et son complément sont récursivement inséparables (dont l'un des deux n'est pas récursivement énumérable). Cependant, il existe de nombreux exemples d'ensembles A et B qui sont disjoints, non complémentaires, et récursivement inséparables. De plus, il est possible que A et B soient récursivement inséparables, disjoints et tous deux récursivement énumérable.
- Soit φ une énumération standard des fonctions partielles calculables. Alors les ensembles A = {e : φe(0) = 0 et B = {e : φe(0) = 1 sont récursivement inséparables[4]. Par l'absurde, s'il existe un séparateur récursif C, alors on peut construire le programme qui commence par calculer si son propre index dans l'énumération est dans C ou C, puis donne respectivement 1 ou 0 en sortie. Dans les deux cas cela contredit son appartenance à B ou A (respectivement).
- Soit # un codage de Gödel standard pour les formules de l'arithmétique de Peano. Alors l'ensemble A = { #(ψ) : PA ⊢ ψ } des formules prouvables et l'ensemble B = { #(ψ) : PA ⊢ ¬ψ } des formules réfutables sont récursivement inséparables. L'inséparabilité des ensembles de formules prouvables et réfutables vaut pour de nombreuses autres théories formelles de l'arithmétique[5].
Références[modifier | modifier le code]
- J. Donald Monk, Mathematical logic, Springer-Verlag, (ISBN 0-387-90170-1, 978-0-387-90170-1 et 3-540-90170-1, OCLC 1974147, lire en ligne), p. 100
- Büchi, J.R. Turing-machines and the Entscheidungsproblem. Math. Ann. 148, 201–213 (1962). https://doi.org/10.1007/BF01470748
- Tennenbaum, S. Inseparable sets and reducibility. Technical Note, University of Michigan, 1961. lien vers le pdf.
- (en) W. Gasarch, « Chapter 16 A survey of recursive combinatorics », dans Studies in Logic and the Foundations of Mathematics, vol. 139, Elsevier, , 1041–1176 p. (ISBN 978-0-444-50106-6, DOI 10.1016/s0049-237x(98)80049-9, lire en ligne), p. 1047, p.
- (de) Raymond M. Smullyan, « Undecidability and recursive inseparability », Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 4, nos 7-11, , p. 143–147 (DOI 10.1002/malq.19580040705, lire en ligne, consulté le )
